package my.algo.data;

/**
 * @author fengbo
 * @date 2018/5/14
 */
public class HashMap<K extends Comparable<K>, V> implements Map<K, V> {

    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    private Entry<K, V>[] table;
    private int size;

    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    public HashMap(int init) {
        table = new Entry[init];
    }

    @Override
    public V get(K key) {
        if (key == null) {
            return null;
        }
        int index = indexFor(key.hashCode(), table.length);
        Entry<K, V> entry = table[index];
        while (entry != null) {
            if (key.equals(entry.key)) {
                return entry.value;
            }
            entry = entry.next;
        }
        return null;
    }

    @Override
    public void put(K key, V value) {
        if (key == null) {
            return;
        }
        int h = key.hashCode();
        int index = indexFor(h, table.length);
        Entry<K, V> entry = table[index];
        while (entry != null) {
            if (key.equals(entry.key)) {
                entry.value = value;
                return;
            }
            entry = entry.next;
        }
        entry = table[index];
        table[index] = new Entry<>(key, value, entry);
        size++;
    }

    @Override
    public void delete(K key) {
        if (key == null) {
            return;
        }
        int index = indexFor(key.hashCode(), table.length);
        Entry<K, V> entry = table[index];
        if (entry != null && key.equals(entry.key)) {
            table[index] = entry.next;
            return;
        }
        while (entry != null) {
            Entry<K, V> temp = entry;
            entry = entry.next;
            if (entry != null && key.equals(entry.key)) {
                temp.next = entry.next;
            }
        }
    }

    @Override
    public boolean contains(K key) {
        return get(key) != null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size > 0;
    }

    @Override
    public List<K> keys() {
        List<K> result = new LinkedList<>();
        for (Entry<K, V> entry : table) {
            while (entry != null) {
                result.add(entry.key);
                entry = entry.next;
            }
        }
        return result;
    }

    private int indexFor(int h, int length) {
        return h % (length - 1);
    }

    private static class Entry<K, V> {
        final K key;
        V value;
        /** 下一个节点 */
        Entry<K, V> next;

        Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        HashMap<Integer, Integer> map = new HashMap<>(6);
        map.put(1, 90);
        map.put(2, 95);
        map.put(3, 85);
        map.put(4, 85);
        map.put(5, 85);
        map.put(6, 85);
        map.put(7, 85);
        map.put(8, 85);
        map.put(9, 85);
        map.put(10, 85);
        map.put(11, 85);
        map.put(12, 85);
        map.put(13, 85);

        map.put(2, 111);

        map.delete(2);

        map.put(2, 888);
        List<Integer> keys = map.keys();


        System.out.println(map.get(1));
        System.out.println(map.get(2));
        System.out.println(map.get(17));
        System.out.println(map.get(null));
    }
}
